import java.util.*;;
/**
 * 
 * 最小的K个数
 * 
 * 描述

给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围：
0
≤
k
,
n
≤
10000
0≤k,n≤10000，数组中每个数的大小
0
≤
v
a
l
≤
1000
0≤val≤1000
要求：空间复杂度 
O
(
n
)
O(n) ，时间复杂度 
O
(
n
l
o
g
k
)
O(nlogk)
 */
public class 最小的K个数 {
    
    public static void main(String[] args) {
        
        int[] nums = new int[]{0,1,2,1,2};
        List<Integer> result = GetLeastNumbers_Solution(nums, 3);

        result.stream().map(s -> s+", ").forEach(System.out::print);
        System.out.println();
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param input int整型一维数组 
     * @param k int整型 
     * @return int整型ArrayList
     */
    public static ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        // write code here

        ArrayList<Integer> result = new ArrayList<>();

        if(0 == k || k>input.length) return result;

        int[] sortedNums = Arrays.stream(input).sorted().toArray();

        for(int i=0; i<k; i++){

            result.add(sortedNums[i]);

        }


        return result;
    }
}
